Introduction to parallel computing: [a practical guide with examples in C]

0198515766......Page 1
Contents......Page 10
List of Figures......Page 16
List of Tables......Page 18
1.1 Memory......Page 20
1.2.1 Cache designs......Page 24
1.2.2 Pipelines, instruction scheduling, and loop unrolling......Page 27
1.4 Networks......Page 34
2.1 Linear algebra......Page 37
2.2 LAPACK and the BLAS......Page 40
2.2.1 Typical performance numbers for the BLAS......Page 41
2.2.2 Solving systems of equations with LAPACK......Page 42
2.3 Linear algebra: sparse matrices, iterative methods......Page 47
2.3.1 Stationary iterations......Page 48
2.3.2 Jacobi iteration......Page 49
2.3.4 Successive and symmetric successive overrelaxation......Page 50
2.3.6 The generalized minimal residual method (GMRES)......Page 53
2.3.7 The conjugate gradient (CG) method......Page 55
2.3.9 The sparse matrix vector product......Page 58
2.3.10 Preconditioning and parallel preconditioning......Page 61
2.4 Fast Fourier Transform (FFT)......Page 68
2.4.1 Symmetries......Page 74
2.5 Monte Carlo (MC) methods......Page 76
2.5.1 Random numbers and independent streams......Page 77
2.5.2 Uniform distributions......Page 79
2.5.3 Non-uniform distributions......Page 83
3.1 Introduction......Page 104
3.2 Data dependencies and loop unrolling......Page 105
3.2.1 Pipelining and segmentation......Page 108
3.2.2 More about dependencies, scatter/gather operations......Page 110
3.2.3 Cray SV-1 hardware......Page 111
3.2.4 Long memory latencies and short vector lengths......Page 115
3.2.6 Pentium 4 architecture......Page 116
3.2.7 Motorola G-4 architecture......Page 120
3.2.8 Branching and conditional execution......Page 121
3.3 Reduction operations, searching......Page 124
3.4.1 Matrix multiply......Page 125
3.4.2 SGEFA: The Linpack benchmark......Page 126
3.5.1 Polynomial evaluation......Page 129
3.5.2 A single tridiagonal system......Page 131
3.5.3 Solving tridiagonal systems by cyclic reduction.......Page 133
3.5.4 Another example of non-unit strides to achieve parallelism......Page 136
3.5.5 Some examples from Intel SSE and Motorola Altivec......Page 141
3.5.6 SDOT on G-4......Page 142
3.5.7 ISAMAX on Intel using SSE......Page 143
3.6 FFT on SSE and Altivec......Page 145
4.2 HP9000 Superdome machine......Page 155
4.3 Cray X1 machine......Page 156
4.4 NEC SX-6 machine......Page 158
4.5 OpenMP standard......Page 159
4.6 Shared memory versions of the BLAS and LAPACK......Page 160
4.7 Basic operations with vectors......Page 161
4.7.1 Basic vector operations with OpenMP......Page 162
4.8 OpenMP matrix vector multiplication......Page 165
4.8.1 The matrix-vector multiplication with OpenMP......Page 166
4.8.2 Shared memory version of SGEFA......Page 168
4.8.3 Shared memory version of FFT......Page 170
4.9 Overview of OpenMP commands......Page 171
4.10 Using Libraries......Page 172
5 MIMD, MULTIPLE INSTRUCTION, MULTIPLE DATA......Page 175
5.1 MPI commands and examples......Page 177
5.2 Matrix and vector operations with PBLAS and BLACS......Page 180
5.3.1 Cyclic vector distribution......Page 184
5.3.2 Block distribution of vectors......Page 187
5.3.3 Block-cyclic distribution of vectors......Page 188
5.4.1 Two-dimensional block-cyclic matrix distribution......Page 189
5.5 Basic operations with vectors......Page 190
5.6.1 Matrix–vector multiplication with MPI......Page 191
5.6.2 Matrix–vector multiply with PBLAS......Page 192
5.7 ScaLAPACK......Page 196
5.8 MPI two-dimensional FFT example......Page 199
5.9 MPI three-dimensional FFT example......Page 203
5.10 MPI Monte Carlo (MC) integration example......Page 206
5.11 PETSc......Page 209
5.11.1 Matrices and vectors......Page 210
5.11.2 Krylov subspace methods and preconditioners......Page 212
5.12 Some numerical experiments with a PETSc code......Page 213
A.2 Boolean and logical intrinsics......Page 220
A.3 Load/store operation intrinsics......Page 221
A.4 Vector comparisons......Page 224
A.7 Integer/floating point vector conversions......Page 225
A.8 Arithmetic function intrinsics......Page 226
B.1 Mask generating vector comparisons......Page 230
B.2 Conversion, utility, and approximation functions......Page 231
B.3 Vector logical operations and permutations......Page 232
B.4 Load and store operations......Page 233
B.5 Full precision arithmetic functions on vector operands......Page 234
B.6 Collective comparisons......Page 235
APPENDIX C: OPENMP COMMANDS......Page 237
D.1 Point to point commands......Page 239
D.2 Collective communications......Page 245
D.3 Timers, initialization, and miscellaneous......Page 253
APPENDIX E: FORTRAN AND C COMMUNICATION......Page 254
APPENDIX F: GLOSSARY OF TERMS......Page 259
APPENDIX G: NOTATIONS AND SYMBOLS......Page 264
References......Page 265
C......Page 274
L......Page 275
M......Page 276
S......Page 277
X......Page 278